/*************************************************************************
	> File Name: insert_sort.cpp
	> Author: 
	> Mail: 
	> Created Time: Mon 05 Aug 2024 02:15:27 PM CST
 ************************************************************************/

#include <cstdio>
#include <cstdlib>
#include "0.sort_test.h"

void insertSort(int *arr, int l, int r) {
    for(int i = l + 1; i < r; i++) {
        int index = i;
        while(index > l && arr[index] < arr[index - 1]) {
            swap(arr[index], arr[index - 1]);
            index--;
        }
    }
    return ;
}

void unguardedInsertSort(int *arr, int l, int r) {
    int index = l;
    for(int i = l + 1; i < r; i++) {
        if(arr[i] < arr[index]) index = i;
    }
    // swap(arr[l], arr[index]); 破坏插入排序稳定
    while(index > l) {
        swap(arr[index], arr[index - 1]);
        --index;
    }
    for(int i = l + 1; i < r; i++) {
        index = i;
        while(arr[index] < arr[index - 1]) {
            swap(arr[index], arr[index - 1]);
            --index;
        }
    }
    return ;
}

int main() {
    int *arr = getRandData(SMALL_DATA);
    TEST(insertSort, arr, SMALL_DATA);
    TEST(unguardedInsertSort, arr, SMALL_DATA);
    free(arr);
    return 0;
}
